#
# @lc app=leetcode.cn id=155 lang=python3
#
# [155] 最小栈
#

# @lc code=start
class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.min_index = 0

    def push(self, x: int) -> None:
        self.stack.append(x)
        if self.stack[self.min_index] > x:
            self.min_index = len(self.stack) - 1

    def pop(self) -> None:
        flag = False
        if self.min_index == len(self.stack) - 1:
            flag = True 
        q = self.stack.pop()
        self.sort()
        return q

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        if len(self.stack) < 0:
            return None
        return self.stack[self.min_index]

    def sort(self):
        if len(self.stack) <=0: return 
        min_index = 0
        for i in range(len(self.stack)):
            if self.stack[i] < self.stack[min_index]:
                min_index = i
        self.min_index = min_index


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()
# @lc code=end

